package leetcode.medium.numofminutes;

import java.util.*;

/**
 * <h4>
 *     <a href="https://leetcode.cn/problems/time-needed-to-inform-all-employees/">
 *         1376. Time Needed to Inform All Employees [Medium]
 *     </a>
 * </h4>
 * <h4>How to solve this question?</h4>
 * <p>
 *     It's a multi-way tree with weight on its nodes. The task is to find a path from the root to one of its leaf
 *     nodes in which the corresponding cumulative path sum is the greatest among all possible paths.<br/>
 *     Use dfs to solve this question.
 * </p>
 */
public class Solution {
    private int res = 0;
    private Map<Integer, Set<Integer>> subManagersMap = new HashMap<>();
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        for (int i = 0; i < manager.length; i++) {
            subManagersMap.putIfAbsent(manager[i], new HashSet<>());
            subManagersMap.get(manager[i]).add(i);
        }
        dfs(informTime, headID, 0);
        return res;
    }

    private void dfs(int[] informTime, int headID, int time) {
        Set<Integer> subManagers = subManagersMap.get(headID);
        if (subManagers == null || subManagers.isEmpty()) {
            res = Math.max(res, time);
            return;
        }
        for (Integer subManager : subManagers) {
            dfs(informTime, subManager, time + informTime[headID]);
        }
    }
}
